package xyz.scootaloo.code.adt;

import java.util.Stack;

/**
 * @author flutterdash@qq.com
 * @since 2021/11/13 15:59
 */
public abstract class AbstractBinarySearchTree<E extends Comparable<? super E>> {

    protected <R extends BinaryNode<E>> KIterator<E> treeIterator(R root) {
        return new BinaryTreeIterator(root);
    }

    @SuppressWarnings("unchecked")
    protected <R extends BinaryNode<E>> R findMin(R current) {
        if (current != null) {
            while (current.left != null)
                current = (R) current.left;
        }
        return current;
    }

    private class BinaryTreeIterator implements KIterator<E> {

        private final Stack<BinaryNode<E>> stack = new Stack<>();

        public BinaryTreeIterator(BinaryNode<E> root) {
            if (root != null)
                stack.push(root);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public E next() {
            BinaryNode<E> top = stack.pop();
            E rtn = top.value;
            if (top.right != null)
                stack.push(top.right);
            if (top.left != null)
                stack.push(top.left);
            return rtn;
        }
    }
}
